package Year21_Month11.day1116;

public class Sort {
    public static void print(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    public static void swap(int a,int b){
        int tmp = a;
        a = b;
        b = tmp;
    }

    public static void selectSort(int[] arr){
        //定义end指针用来交换最大值
        int end = arr.length - 1;
        while(end > 0){
            int key = 0;//假设0号下标最大
            //找最大数字
            for(int i = 0; i <= end;i++){
                if(arr[i] > arr[key]){
                    key = i;
                }
            }
            //如果说最大值下标不是最后一位未排序的元素，那么就进行交换
            if(key != end){
                int tmp = arr[key];
                arr[key] = arr[end];
                arr[end] = tmp;
            }
            end--;
        }
    }
    //===============================================================================================
    //构造一个堆
    //向下调整
    public static void swap(int[] arr,int left,int right){
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
    public static void shiftDown(int[] arr,int size,int parent){//bound是边界，就是向下调整的最后一个可调整的节点的位置
        int child = parent * 2 + 1;
        while(child < size){
            if(child + 1 < size && arr[child + 1] > arr[child]){
                child += 1;
            }
            if(arr[parent] < arr[child]){
                swap(arr,parent,child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                return;
            }
        }
    }
   public static void heapSort(int[] arr){
        int size = arr.length;
        for(int root = (arr.length-2)/2; root >= 0; root--){
           shiftDown(arr, arr.length, root);
       }
        int end = size - 1;
        while(end != 0){
            swap(arr,0,end);
            shiftDown(arr,end,0);
            end--;
        }
   }

    public static void main(String[] args) {
        int[] arr = {4,2,8,6,9,1,3,5,0,7};
        //selectSort(arr);
        heapSort(arr);
        print(arr);
    }
}
